20220224-TIL
February 24, 2022
오늘 알고리즘 문제는 히스토그램 내부에 있는 가장 넓은 직사각형 공간의 넓이를 구하는 문제였다.
- 히스토그램에서 가장 큰 직사각형 문제는 모든 직사각형 형태의 공간을 확인하는 식으로 풀었다.
- 처음에는 연결할 수 있는 모든 직사각형을 하나씩 연결하는 식으로 접근했다. (약간 그리디하게)
- 직사각형을 하나씩 확인하면서, 연결할 수 있는 직사각형이 있으면 스택에 저장하도록 구현했다.
- 스택에는, 직사각형의 높이와 너비를 저장하고, 직사각형을 연결할 때마다 갱신하도록 구현했다.
- 현재 직사각형의 높이가 스택 맨 뒤에 있는 직사각형의 높이보다 크면, 그대로 스택에 저장했다.
- 작다면, 스택에 저장된 직사각형을 하나씩 연결하고, 최대 넓이와 높이, 너비를 갱신하도록 했다.
카카오 신입공채 2차 코딩 테스트 문제 해설 내용을 정리했다. ( 풀어보질 않아서 이해가 잘 안된다;)
# TIL